Sejf
Limit pamięci: 32 MB
Bajtazar jest słynnym kasiarzem, który porzucił przestępczy żywot i zajął
się testowaniem zabezpieczeń antywłamaniowych.
Właśnie dostał do sprawdzenia nowy rodzaj sejfu: kombinatoryczny.
Sejf jest otwierany pokrętłem, które kręci się w kółko.
Można je ustawić w
różnych pozycjach ponumerowanych od 0 do
.
Ustawienie pokrętła w niektórych pozycjach powoduje otwarcie sejfu, a w innych nie.
Przy tym, pozycje otwierające sejf mają taką własność, że jeżeli
i
są takimi pozycjami,
to
też powoduje otwarcie sejfu (dotyczy to także przypadku, gdy
).
Bajtazar sprawdził
różnych pozycji pokrętła:
.
Pozycje
nie powodują otwarcia sejfu,
dopiero ustawienie pokrętła w pozycji
spowodowało jego otwarcie.
Bajtazarowi nie chce się sprawdzać wszystkich pozycji pokrętła.
Chciałby wiedzieć, na podstawie do tej pory sprawdzonych pozycji, jaka jest maksymalna możliwa liczba pozycji,
w których pokrętło otwiera sejf.
Pomóż mu i napisz odpowiedni program.
Wejście
Pierwszy wiersz standardowego wejścia zawiera dwie liczby całkowite
oraz
oddzielone pojedynczym odstępem,
,
.
W drugim wierszu znajduje się
różnych liczb całkowitych, pooddzielanych
pojedynczymi odstępami,
,
.
Możesz założyć, że dane wejściowe odpowiadają pewnemu sejfowi spełniającemu
warunki zadania.
W testach wartych ok. 70% punktów zachodzi
.
W części tych testów, wartych ok. 20% punktów, zachodzą dodatkowo warunki
oraz
.
Wyjście
Twój program powinien wypisać w pierwszym (i jedynym) wierszu standardowego
wyjścia jedną liczbę całkowitą: maksymalną liczbę pozycji pokrętła,
które mogą powodować otwarcie sejfu.
Przykład
Dla danych wejściowych:
42 5
28 31 10 38 24
poprawną odpowiedzią jest:
14
Autor zadania: Marian M. Kędzierski.